/*
 * @lc app=leetcode.cn id=1981 lang=cpp
 *
 * [1981] 最小化目标值与所选元素的差
 */

// @lc code=start
class Solution
{
public:
    int minimizeTheDifference(vector<vector<int>> &mat, int target)
    {
        int m = mat.size(), n = mat[0].size(), sum = 0;
        unordered_set<int> s[2];
        for (auto num : mat[0])
        {
            s[0].insert(num);
            sum = max(sum, num);
        }
        for (int i = 1; i < m; i++)
        {
            int maxNum = 0;
            for (auto num : mat[i])
            {
                maxNum = max(maxNum, num);
            }
            sum += maxNum;

            int idx = i % 2, preIdx = (i - 1) % 2;
            s[idx].clear();

            for (int j = i + 1; j <= sum; j++)
            {
                for (auto num : mat[i])
                {
                    if (s[preIdx].count(j - num) == 0)
                        continue;
                    s[idx].insert(j);
                    break;
                }
            }
        }
        int ans = __INT_MAX__;
        for (auto num : s[(m - 1) % 2])
        {
            ans = min(ans, abs(num - target));
        }
        return ans;
    }
};
// @lc code=end
